package com.cat.greedyAlgorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/reduce-array-size-to-the-half/description/
 * @create 2025/8/21 09:36
 * @since JDK17
 */

public class Solution01 {
    public int minSetSize(int[] arr) {
        int ans = arr.length / 2;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {   // 计数
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer> cnts = new ArrayList<>();
        for (Integer value : map.values()) {
            cnts.add(value);
        }
        Collections.sort(cnts);
        for (int i = cnts.size() - 1; i >= 0; i--) {
            ans -= cnts.get(i);
            if (ans <= 0) {
                return cnts.size() - i;
            }
        }
        return -1;
    }
}
